import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025-02-10
 * Time: 14:03
 */
public class BinaryTree {
    //二叉表示法
    public static class BTNode {
        BTNode left;//左孩子的引用
        BTNode right;//右孩子的引用
        int val;//数据域

        public BTNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return val + " ";

        }
    }

    //手动创建二叉树
    public BTNode createBinaryTree(){
        BTNode btNode1 = new BTNode(1);
        BTNode btNode2 = new BTNode(2);
        BTNode btNode3 = new BTNode(3);
        BTNode btNode4 = new BTNode(4);
        BTNode btNode5 = new BTNode(5);
        BTNode btNode6 = new BTNode(6);
        BTNode btNode7 = new BTNode(7);
        BTNode btNode8 = new BTNode(8);
        btNode1.left = btNode2;
        btNode2.left = btNode4;
        btNode2.right = btNode5;
        btNode1.right = btNode3;
        btNode3.left = btNode6;
        btNode3.right = btNode7;
        btNode4.left = btNode8;
        return btNode1;
    }
    //前序遍历
    public void preOrder(BTNode root){
        if (root == null) return;
        //打印当前节点
        System.out.print(root.val+" ");
        //遍历左树
        preOrder(root.left);
        //遍历右树
        preOrder(root.right);
    }
    //中序遍历
    public void inOrder(BTNode root){
        if (root == null) return;
        //遍历左树
        inOrder(root.left);
        //打印当前节点
        System.out.print(root.val+" ");
        //遍历右树
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(BTNode root){
        if (root == null) return;
        //遍历左树
        postOrder(root.left);
        //遍历右树
        postOrder(root.right);
        //打印当前节点
        System.out.print(root.val+" ");
    }
    // 获取树中节点的个数
    public int size(BTNode root){
        if (root == null) return 0;
        return (size(root.left) + size(root.right) + 1);
    }
    // 获取叶子节点的个数
    public int getLeafNodeCount(BTNode root){
        if (root == null) return 0;
        if( root.left == null && root.right == null) return  1;
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    // 获取第K层节点的个数
    public int getKLevelNodeCount(BTNode root,int k){
        if (root == null) return 0;
        if (k == 1) return 1;
        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
    }
    // 获取二叉树的高度
    public int getHeight(BTNode root){
        if (root == null) return 0;
        int countLeft = getHeight(root.left);
        int countRight = getHeight(root.right);
        return (countLeft >= countRight ? countLeft + 1 : countRight + 1);
    }
    // 检测值为value的元素是否存在
    public Boolean findValue(BTNode root, int val){
        if (root == null) return false;
        if (root.val == val) return true;
        if(findValue(root.left,val)) return true;
        if(findValue(root.right,val)) return true;
        return false;
    }
    //层序遍历初阶
    public void levelOrder(BTNode root){//两种
        if (root == null) return;
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    //层序遍历进阶
    public List<List<BTNode>> levelOrder2(BTNode root){//两种
        List<List<BTNode>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<BTNode> temp = new ArrayList<>();
            while (size != 0) {
                BTNode cur = queue.poll();
                temp.add(cur);
                size--;
                if (cur != null && cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur != null && cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(temp);
        }
        return ret;
    }
    //判断完全二叉树
    public Boolean isCompleteTree (BTNode root){
        if (root == null) return true;
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            if (cur != null) return false;
        }
        return true;
    }
    //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
    /*public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(p == root || q == root) return root;
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        if(leftNode != null && rightNode != null){
            return root;
        }else if(rightNode == null){
            return leftNode;
        }else{
            return rightNode;
        }
    }*/
    /*public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null) return null;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);

        if(stack1.size() > stack2.size()){
            int size = stack1.size() - stack2.size();
            while(size > 0){
                stack1.pop();
                size--;
            }
        }else{
            int size = stack2.size() - stack1.size();
            while(size > 0){
                stack2.pop();
                size--;
            }
        }
        while(!stack1.isEmpty() && !stack2.isEmpty()){
            if(stack1.peek().equals(stack2.peek())) return stack1.peek();
            stack1.pop();
            stack2.pop();
        }
        return null;
    }
    private boolean getPath(TreeNode root, TreeNode node,Stack<TreeNode> stack){
        if(root == null || node == null) return false;
        stack.push(root);
        if(root == node) return true;
        boolean flg1 = getPath(root.left,node,stack);
        if(flg1) return true;
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2) return true;
        stack.pop();
        return false;
    }*/
    //根据一棵树的前序遍历与中序遍历构造二叉树
    /*public int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd){
        if(inBegin > inEnd) return null;

        TreeNode root = new TreeNode(preorder[preIndex]);

        int findIndex = find(inorder,inBegin,inEnd,preorder[preIndex]);
        if(findIndex == -1 ) return null;

        preIndex++;
        root.left = buildTreeChild(preorder,inorder,inBegin,findIndex-1);
        root.right = buildTreeChild(preorder,inorder,findIndex+1,inEnd);

        return root;
    }

    public int find(int[] inorder,int inBegin,int inEnd,int key){
        for(int i = inBegin;i <= inEnd;i++){
            if(inorder[i] == key)
                return i;
        }
        return -1;
    //根据一棵树的中序遍历与后序遍历构造二叉树
    }*/
    /*public int postIndex;

    public TreeNode buildTree(int[] postIndex, int[] inorder) {
        postIndex = inorder.length - 1;
        return buildTreeChild(postorder,inorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] postorder,int[] inorder,int inBegin,int inEnd){
        if(inBegin > inEnd) return null;

        TreeNode root = new TreeNode(postorder[postIndex]);

        int findIndex = find(inorder,inBegin,inEnd,postorder[postIndex]);
        if(findIndex == -1 ) return null;

        postIndex--;
        root.left = buildTreeChild(postorder,inorder,inBegin,findIndex-1);
        root.right = buildTreeChild(postorder,inorder,findIndex+1,inEnd);

        return root;
    }

    public int find(int[] inorder,int inBegin,int inEnd,int key){
        for(int i = inBegin;i <= inEnd;i++){
            if(inorder[i] == key)
                return i;
        }
        return -1;
    }*/
    //二叉树创建字符串
    public String tree2str(BTNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void tree2strChild(BTNode root,StringBuilder stringBuilder){
        if(root == null) return;
        stringBuilder.append(root.val);
        if(root.left != null){
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(root.right != null){
                stringBuilder.append("()");
            }else{
                return;
            }
        }
        if(root.right != null){
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            return;
        }
    }
    //非递归前序遍历
    public void preOrder2(BTNode root){
        if(root == null) return;
        Stack<BTNode> stack = new Stack<>();
        BTNode cur = root;
        BTNode top;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur = cur.left;
            }
            top = stack.pop();
            cur = top.right;
        }
        System.out.println();
    }
    //非递归中序遍历
    public void inOrder2(BTNode root){
        if(root == null) return;
        Stack<BTNode> stack = new Stack<>();
        BTNode cur = root;
        BTNode top;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.pop();
            System.out.print(top.val+" ");
            cur = top.right;
        }
        System.out.println();
    }
    //后序遍历
    public void postOrder2(BTNode root){
        if(root == null) return;
        Stack<BTNode> stack = new Stack<>();
        BTNode cur = root;
        BTNode top;
        BTNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.peek();
            if (top.right == null || prev == top.right) {
                top = stack.pop();
                System.out.print(top.val+" ");
                prev = top;
            }else {
                cur = top.right;
            }
        }
        System.out.println();
    }
}